package zuo.highLevel_4;

/**
 * @Author: Forx
 * @Data: 2021/7/5
 * @Desc: Algorithm - zuo.highLevel_4
 * @Version: v1.0
 */

/**
 * 给定一个NX3的矩阵matrix,对于每一个长度为3的小数组arr,都表示一个大楼的三个数
 * 据。arr[0]表示大楼的左边界，arr[1]表示大楼的右边界，arr[2]表示大楼的高度（一定大于0)。
 * 每座大楼的地基都在X轴上，大楼之间可能会有重叠，请返回整体的轮廓线数组。
 * 【举例】
 * matrix={
 * {2,5,6},
 * {1,7,4},
 * [4,6,7},
 * [3,6,5],
 * {10,13,2},
 * {9,11,3},
 * [12,14,4},
 * {10,12,5}
 * 返回：
 * 返回数组的表达形式和输入一样,arr[0]是左边界,arr[1]是右边界,arr[2]是高
 * matrix={
 * {{1,2,4},
 * {2,4,6},
 * {4,6,7},
 * {6,7,4},
 * {9,10,3},
 * {10,12,5},
 * {12,14,4}}
 * */
/**
 *  给定一个数组arr,该数组无序，但每个值均为正数，再给定一个正数k。求arr的
 * 所有子数组中所有元素相加和为k的最长子数组长度。
 * 例如，arr=[1,2,1,1,1],k=3。
 * 累加和为3的最长子数组为[1,1,1],所以结果返回3。
 * 要求：时间复杂度0(N),额外空间复杂度0(1)
 * */
class maxSumSub{
    //不对,人说的是子数组,必须连续
    private int getMaxSumSub(int[] arr,int sum){
        return process(arr,0,sum);
    }
    private int process(int[] arr,int left,int sum){
        if(sum==0)return 1;
        if(left==arr.length-1){
            if(arr[left]==sum){
                return 1;
            }else {
                return 0;
            }
        }
        int len1 = process(arr,left+1,sum-arr[left])+1;
        int len2 = process(arr,left+1,sum);
        return Math.max(len1,len2);
    }

    private int getMaxSubSumLen(int[] arr,int sum){
        int len = process2(arr,0,sum,true);
        len = len==-1?0:len;
        return Math.max(len,process2(arr,0,sum,false));
    }
    /*
    * 太麻烦了,时间复杂度太高了
    * */
    private int process2(int[] arr,int left,int sum,boolean isContinuous){
        if(sum==0){
            return 0;
        }
        if(left == arr.length-1){
            return arr[left]==sum?1:isContinuous?-1:0;
        }
        if(isContinuous){
            if(sum <0)return -1;
            int ans =  process2(arr,left+1,sum-arr[left],true);
            if(ans==-1){
                return -1;
            }
            return ans+1;
        }else {
            int ans1 = process2(arr,left+1,sum-arr[left],true);
            int ans2 = process2(arr,left+1,sum,false);
            if(ans1==-1)return ans2;
            if(ans2==-1) return ans1;
            return Math.max(ans1+1,ans2);
        }
    }
    /*
    * 左右指针动
    * */

    public void test(){
        int[] buff = {1,2,1,2,1};
        //System.out.println(getMaxSumSub(buff,3));
        System.out.println(getMaxSubSumLen(buff,7));
    }


}

/**
 * 一个无序数组,其中元素可正可负,可0,给定k求arr所有子数组中累加和小于或等于k的最长子数组长度
 *  minSum数组和minSumEnd数组
 *
 * */

public class HL4 {
    public static void main(String[] args) {
        maxSumSub maxSumSub = new maxSumSub();
        maxSumSub.test();

    }
}
